In any digital signature scheme, each user has a pair of matching verification and signing keys. A user U produces his digital signature of a message M by running a special algorithm on inputs Chat include M and his signing key. Of course, it is important that the signing key be kept secret by the user. User U's digital signature of a message M can be verified by running an algorithm whose inputs include the digital signature and U's verification key. The user's verification key must be as "public" as possible to allow as universal as possible verification of U's digital signatures. For these reasons, U's verification key is also referred to as U's public key, and the corresponding signing key as U's secret key.
The question of how a user can make his own public key truly public is an important problem. One solution, namely, having each user post his own verification key in a widely accessible file (e.g., a conventional or electronic data base), is not a satisfactory solution for two reasons. First, it may be inconvenient to retrieve U's public key from such a list when a verifier is presented with U's digital signature of a given message. Second, because a malicious user W may compute a pair of matching verification and signing keys (V and S) and post V as U's verification key, the malicious user may be able to digitally-sign messages that will be believed to be coming from U. It is thus important that whenever a given user wishes to post or otherwise publicize a key V as his verification key, there must be a way to correctly determine that the user in fact elects V as his verification key. This is the requirement that each public key in a digital signature scheme be properly "certified."
Techniques for building certificates of public keys are known in the art. The traditional way envisions a hierarchy of authorities. For example, assume that there is a simple two-level hierarchy: a few thousand first-level authorities, A'.sub.1,A'.sub.2, . . . , and a single second-level authority, A". It is assumed that each of the first-level authorities is capable of digitally signing, that their public keys, PK'.sub.1,PK'.sub.2, . . . , are already known to A", and that the public-key of A", PK", is universally known. When a user U wishes to have his chosen public key, PK.sub.U, certified, he goes to the authority, A'.sub.c, closest to (or most convenient for) him. After verifying U's identity and the fact that he wishes to elect PK.sub.U as his own signing key (alternatively, A'.sub.c may receive a traditional notarized document to this effect), A'.sub.c provides U with a certificate consisting of (1) his own digital signature of PK.sub.U (relative to PK'.sub.c) (2) his own public key PK'.sub.c and (3) the digital signature of A" of PK'.sub.c (relative to PK".) The second and third pieces of data are necessary since there may be a sufficiently-high number of first-level authorities and their public keys may not be universally known. Such a certificate is either given to user U, so that he will send it along with any digital signature of his (in order to enable anyone to verify it), or the certificate is posted in a sufficiently accessible database (so that anyone who wishes verify U's digital signature of a given message can retrieve the certificate of U's public key from the database).
In either case, a traditional certificate for PK.sub.U is quite long because it includes at least two pieces of data in addition to the signature of PK.sub.U. This is undesirable, since public-key certificates must be sent along or retrieved with almost every single digital signature. Moreover, the recipient of a digital signature may wish to store its associated public-key certificate for a long time period to maintain proof of the signer's commitment. Such long certificates are thus very costly, because sending bits across communication lines (e.g., via a long-distance phone call) is expensive and because storing bits is expensive. Obviously the longer the certificate, the higher the cost associated with transmission and storage thereof.
Another problem associated with the prior art certification techniques is that such schemes provide no way for inspecting that the user U knows the secret signing key corresponding to a verification key. In particular, before an authority agrees to certify or to participate in the certification of the verification key presented by the user U, it may be important to inspect that U knows the secret signing key corresponding thereto. For example, assume a legitimate user U has already obtained a certificate that PK.sub.U is his public key. Then, a malicious user V may go to a competent authority with PK.sub.U claiming that he wishes to have this string certified as his own public key. Even if the authority verifies the identity of V, nothing so far prevents that PK.sub.V may be also certified as V's public key. While V's action may not enable him to cheat as he pleases (because he ignores PK.sub.U 's matching secret key), the situation may still be quite dangerous. For instance, if it determined from other transactions that the owner of public key PK.sub.U is entitled to certain rights, then V may claim those rights for himself by exhibiting easily-obtained "certificate" that PK.sub.U is his key. As another example, V might begin by taking a message signed by U relative to PK.sub.U. By adding to this signature the easily-obtained "certificate" that he owns PK.sub.U, V can appear able to sign relative to PK.sub.U. This cheating and confusion can cause significant problems, but traditional certificate schemes have heretofore not addressed this problem adequately.
There is thus a need to provide a new and efficient method of certifying public keys that produces very short and thus very inexpensive certificates and that further ensures that a user presenting a given verification key for certification has legitimately chosen it.